2020 Algorithm                     < No.5  Oil Search>                   Prof. Zoh Q.

2022 Algorithm                       < No.7   클리닝>                   Prof. Zoh Q.

클리닝

[문제]   고급 주택의 청소만을 전문으로 하는 벤처 기업 프리랜서 HCC(House Cleaning Company)가 있다. 이 업체는 소비자들의 요청을 미리 받아서 그중에서 이익이 최대가 되도록 일정을 잡는다.

프리랜서 (freelancer). 중세 유럽에서, 어떠한 국가ㆍ당파ㆍ주의에도 속하지 아니하고 자유롭게 보수를 받으며 군무에 종사하던 기사(騎士).

작업 단위는 일(daily) 단위이며 365*3(년)까지의 일정을 그전에 모두 확정한다. 청소를 요청하는 고객들은 집 청소를 원하는 기간(일단위)와 그때 지불할 비용을 HCC의 신청 Web을 통하여 등록한다. 집 청소를 신청한 고객을 [eqn: i]라고 할 때 그 신청 정보는 [eqn: (b _{i} ``,`e _{i} ``,``c _{i} )]로 표현된다. [eqn: b _{i}]는 작업의 시작일, [eqn: e _{i}]는 종료일(단 [eqn: b _{i`} < e_i]이다. [eqn: c_i]는 제시한 청소의 비용(cost, 만원)을 나타낸다. 각 입력값은 다음과 같은 조건을 만족한다. [eqn: 1` LEQ `b _{i} `` < `e _{i} LEQ 365 CDOT 3]을 항상 만족한다. 따라서 신청할 경우 최소 작업 기간은 하루(a day)이다.

요청하는 청소의 정도, 대상물과 집의 크기 등의 정보를 입력하면 시스템에서 해당 작업 일수를 계산해준다.

HCC는 1인 기업이므로 특정 시간에 두 군데 이상의 작업을 동시에 할 수 없다. 그리고 한번 시작한 작업은 해당 집의 작업이 완전히 끝날 때까지 중지하지 못한다. 그런데 한 집을 마치고 다른 집으로 작업 장소를 바꿀 때마다 청소, 정리 정돈, 재료 보충, 이동 교통비 등의 작업에 비용(손실)이 발생한다. 이 문제에서는 작업 장소를 바꿀 때마다 균일하게 10만원의 부가 비용이 발생한다고 가정한다. 따라서 같은 이득이라면 가능한 작업 장소의 개수를 줄이는 것이 더 이득이 된다.       HCC는 조건을 만족하는 선에서 최대 이익을 확보하기 위하여 작업 일정을 꼼꼼하게 계산해야 한다. 그리고 작업 장소를 옮길 때마다 감수해야 하는 이동, 준비작업으로 소비되는 추가 비용 10만원까지도 반드시 고려해야 한다.

만일 같은 액수의 이익을 보장하는 일정이 하나 이상 존재하면 그 중에서 작업하는 일수가 제일 적은 것을 선택해야 한다. 예를 들어 두 일정 A, B 모두가 200만원을 보장하는데, A는 8일간, B는 6일간 일을 하는 것이라면 당연히 B를 더 선호한다.

하루에 하는 작업의 분량은 빡세겠지만(?), 그래도 쉬는 날이 하루라도 더 늘어나는 것이 언제나 정답이다

출력으로는 최대로 얻을 수 있는 이득 P와 그것을 위한 최소 작업일 수(minimum working days for the max profit) D, 이 두 개의 정수 P, D를 출력해야 한다. 단 이득계산에는 이동 비용손실(회당 10만원)까지 고려되어야 한다. 이 문제를 Dynamic Programming을 활용하는 전형적인 문제이므로 잘 익혀두어야 한다. 다양한 응용이 가능하기 때문이다.

[입출력] 입출력은 모두 stdin과 stdout이다. 입력 파일의 첫 줄에는 신청한 작업의 수 [eqn: N]이 들어온다. ( [eqn: 3 LEQ N LEQ 100]) 이어지는 [eqn: N]개의 줄에는 각 요청한 청소작업의 정보 [eqn: (b _{i} ``,`e _{i} ``,``c _{i} )]을 나타내는 3개의 정수가 한 줄에 나타난다. 출력은 2개의 정수 P, D로 구성된다.

P는 최대 이익(만원), Q는 그 이익을 달성하기 위해서 일을 해야 하는 최소의 날짜 수이다. 한 집의 청소를 마치고 새로운 의뢰인의 집으로 이동할 때마다 10만원의 비용이 들어가므로 이 값은 받은 금액에서 공제해야만 한다. 이렇게 이동 비용까지 모두 공제하고 남은 비용이 실제 얻을 수 있는 이익이고 이것을 출력해야 한다.

stdin	stdout
7 // 7개의 요청 1 4 45 7 9 35 3 7 75 8 9 15 2 5 67 4 6 32 8 9 15	94 9
4 // 4개의 요청 1 4 45 7 9 35 3 7 75 8 9 15	80 7

일자	D1	D2	D3	D4	D5	D6	D7	D8	D9
요청된 작업 일정	U1 ( 1, 4, 45 )						U2 ( 7, 9, 35 )
			U3 ( 3, 7, 75 )
		U5 ( 2, 5, 67 )
	U7 (1, 2, 24 )			U6 ( 4, 6, 32 )				U4 (8, 9, 15 )

[제한조건] 프로그램 이름은 clean.{c,cpp,py, java}이다. 제출은 15번까지 가능하며 최대 허용 수행시간은 NESPA에서 2초이며 이는 언어에 상관없이 모두 동일하다. resursion으로 짜면 시간을 초과할 수 있기 때문에 최대한 Table을 이용하여, 공간을 더 사용하고 시간을 줄이는 방법을 생각해야 한다.